package com.fanco.learn_datastruct_leetcode.leetcode;

/**
 * @author qiaowang 2021/4/22
 * <p>
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 * <p>
 * 输入：s = "babad"
 * 输出："bab"
 * 解释："aba" 同样是符合题意的答案。
 * <p>
 * 输入：s = "cbbd"
 * 输出："bb"
 */
public class Day05 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        String result = solution.longestPalindrome("hdcabacdi");
        System.out.println(result);
    }
    private static class Solution {
        public String longestPalindrome(String s) {
            // 1. 判空
            if ((s == null) || (s.length() < 0)) {
                return "";
            }
            // 初始化 最长回文字符串的 起点和终点
            int start = 0;
            // 初始化 最长回文字符串的 起点和终点
            int end = 0;
            for (int i = 0; i < s.length(); i++) {
                // 考虑奇偶数长度字符串的情况。
                // 1. 奇数长度：它的中心为一位，因此left 和 right都是一样的
                int len1 = expandRoundCenter(s, i, i);
                // 2. 偶数长度，它的中心位为两位，left 比right少一位。
                int len2 = expandRoundCenter(s, i, i + 1);
                int len = Math.max(len1, len2);
                if (len > (end - start)) {
                    // a d c a b a c d h
                    // 如图例子。 len = 7  i= 4
                    // 所以回文串起点是  d 坐标为 1 = 4 - （7-1）/2
                    // 回文串终点是 d 坐标为 4 + 7/2 = 7
                    start = i - ((len - 1) / 2);
                    end = i + (len / 2);
                }
            }
            return s.substring(start, end + 1);
        }
        private int expandRoundCenter(String s, int left, int right) {
            while ((left >= 0) && (right < s.length()) &&
                    (s.charAt(left) == s.charAt(right))) {
                right++;
                left--;
            }
            // 当right, left 不满足时， right和left 分别做了 ++ 和 --的操作。
            // 因此 right - (left+1)  - 2
            // 要去掉最后两个。
            return right - left - 1;
        }
    }
}
